package 牛客网在线编程题库;

/**
 * 题目描述
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
*
 * 示例1
 * 输入
 * 4
 * 返回值
 * 3
 */

public class _斐波那契数列 {
    public static void main(String[] args) {
        int n = 4;
        int target = Fibonacci1(n);
        System.out.println(target);
    }

    /**
     * 递归
     * @param n
     * @return
     */
    public static int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }else{
            return Fibonacci(n - 2) + Fibonacci(n - 1);
        }
    }

    /**
     * 循环非递归
     * @param n
     * @return
     */
    public static int Fibonacci1(int n) {
        // 定义一二三仨数
        int num1 = 0;
        int num2 = 1;
        int num3 = -1;
        if (n == 0) {
            return 0;
        }else if (n == 1) {
            return 1;
        }
        for (int i = 0 ; i <= n - 2 ; i++) {
            num3 = num1 + num2;
            num1 = num2;
            num2 = num3;
        }
        return num3;
    }
}
